import java.util.LinkedList;
import java.util.Queue;

public class Codec {
    public String serialize(TreeNode root) {
        StringBuilder sb=new StringBuilder();
        if(root==null){

            return "[null]";
        }else {
            Queue<TreeNode> queue=new LinkedList<>();
            queue.add(root);
            while (queue.size()>0){
                int num=queue.size();
                for (int i=0;i<num;i++){
                    TreeNode t=queue.poll();
                    if(t==null){
                        sb.append("null,");
                    }else {
                        sb.append(t.val+",");
                        queue.add(t.left);
                        queue.add(t.right);
                    }
                }
            }
            String s=sb.toString();
            s=s.substring(0,s.length()-1);
            int index=s.lastIndexOf("null");
            int len=s.length()-index;
            while (index>0&&len==4){
                s=s.substring(0,s.length()-5);
                index=s.lastIndexOf("null");
                len=s.length()-index;
            }
            return "["+s+"]";
        }
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        data = data.trim();
        data = data.substring(1, data.length() - 1);
        if (data.length() == 0) {
            return null;
        }

        String[] parts = data.split(",");
        String item = parts[0];
        if(item==null||item.equals("")||item.equals("null")){
            TreeNode root=null;
            return root;
        }
        TreeNode root = new TreeNode(Integer.parseInt(item));
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        nodeQueue.add(root);

        int index = 1;
        while(!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.remove();

            if (index == parts.length) {
                break;
            }

            item = parts[index++];
            item = item.trim();
            if (!item.equals("null")) {
                int leftNumber = Integer.parseInt(item);
                node.left = new TreeNode(leftNumber);
                nodeQueue.add(node.left);
            }

            if (index == parts.length) {
                break;
            }

            item = parts[index++];
            item = item.trim();
            if (!item.equals("null")) {
                int rightNumber = Integer.parseInt(item);
                node.right = new TreeNode(rightNumber);
                nodeQueue.add(node.right);
            }
        }
        return root;
    }
}
